﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Numerics;
using System.Diagnostics;

namespace BitcoinLibrary
{
    /**
    * A block is the foundation of the BitCoin system. It records a set of {@link Transaction}s together with
    * some data that links it into a place in the global block chain, and proves that a difficult calculation was done
    * over its contents. See the BitCoin technical paper for more detail on blocks.<p>
    *
    * To get a block, you can either build one from the raw bytes you can get from another implementation,
    * or request one specifically using {@link Peer#getBlock(byte[])}, or grab one from a downloaded {@link BlockChain}.
    */
    public class Block : Message
    {
        //private static readonly Logger log = LoggerFactory.getLogger(Block.class);
        private static readonly long serialVersionUID = 2738848929966035281L;

        /** How many bytes are required to represent a block header. */
        public static readonly int HEADER_SIZE = 80;

        static readonly long ALLOWED_TIME_DRIFT = 2 * 60 * 60; // Same value as official client.

        /** A value for difficultyTarget (nBits) that allows half of all possible hash solutions. Used in unit testing. */
        public static readonly long EASIEST_DIFFICULTY_TARGET = 0x207fFFFFL;

        // For unit testing. If not zero, use this instead of the current time.
        static long fakeClock = 0;
        private long version;
        private byte[] prevBlockHash;
        private byte[] merkleRoot;
        private long time;
        private long difficultyTarget; // "nBits"

        private long nonce;

        /** If null, it means this object holds only the headers. */
        internal List<Transaction> transactions;
        /** Stores the hash of the block. If null, getHash() will recalculate it. */
        private byte[] hash;

        /** Special case constructor, used for the genesis node and unit tests. */
        public Block(NetworkParameters param)
            : base(param)
        {
            // Set up a few basic things. We are not complete after this though.
            version = 1;
            difficultyTarget = 0x1d07fff8L;
            time = Utils.ConvertToTimestamp(DateTime.Now);  // TODO: ok? System.currentTimeMillis() / 1000;
            prevBlockHash = new byte[32]; // All zeros.
        }

        /** Constructs a block object from the BitCoin wire format. */
        public Block(NetworkParameters param, byte[] payloadBytes)
            : base(param, payloadBytes, 0)
        {
        }

        public override void parse()
        {
            version = readUint32();
            prevBlockHash = readHash();
            merkleRoot = readHash();
            time = readUint32();
            difficultyTarget = readUint32();
            nonce = readUint32();

            hash = Utils.reverseBytes(Utils.doubleDigest(bytes, 0, cursor));

            if (cursor == bytes.Length)
            {
                // This message is just a header, it has no transactions.
                return;
            }

            int numTransactions = (int)readVarInt();
            transactions = new List<Transaction>(numTransactions);
            for (int i = 0; i < numTransactions; i++)
            {
                Transaction tx = new Transaction(param, bytes, cursor);
                transactions.Add(tx);
                cursor += tx.getMessageSize();
            }
        }

        private void writeHeader(Stream stream)
        {
            Utils.uint32ToByteStreamLE(version, stream);
            stream.Write(Utils.reverseBytes(prevBlockHash), 0, prevBlockHash.Length);
            stream.Write(Utils.reverseBytes(getMerkleRoot()), 0, getMerkleRoot().Length);
            Utils.uint32ToByteStreamLE(time, stream);
            Utils.uint32ToByteStreamLE(difficultyTarget, stream);
            Utils.uint32ToByteStreamLE(nonce, stream);
        }

        public override void bitcoinSerializeToStream(Stream stream)
        {
            writeHeader(stream);
            // We may only have enough data to write the header.
            if (transactions == null) return;
            var data = new VarInt(transactions.Count).encode();
            stream.Write(data, 0, data.Length);
            foreach (Transaction tx in transactions)
            {
                tx.bitcoinSerializeToStream(stream);
            }
        }

        /**
        * Calculates the block hash by serializing the block and hashing the resulting bytes.
        */
        private byte[] calculateHash()
        {
            try
            {
                MemoryStream bos = new MemoryStream();
                writeHeader(bos);
                return Utils.reverseBytes(Utils.doubleDigest(bos.ToArray()));
            }
            catch (IOException e)
            {
                throw e; // Cannot happen.
            }
        }

        /**
        * Returns the hash of the block (which for a valid, solved block should be below the target) in the form seen
        * on the block explorer. If you call this on block 1 in the production chain, you will get
        * "00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048".
        */
        public String getHashAsString()
        {
            return Utils.bytesToHexString(getHash());
        }

        /**
        * Returns the hash of the block (which for a valid, solved block should be below the target). Big endian.
        */
        public byte[] getHash()
        {
            if (hash == null)
                hash = calculateHash();
            return hash;
        }

        /** The number that is one greater than the largest representable SHA-256 hash. */
        static private BigInteger LARGEST_HASH = BigInteger.One << 256;

        /**
        * Returns the work represented by this block.<p>
        *
        * Work is defined as the number of tries needed to solve a block in the average case. Consider a difficulty
        * target that covers 5% of all possible hash values. Then the work of the block will be 20. As the target gets
        * lower, the amount of work goes up.
        */
        public BigInteger getWork()
        {
            BigInteger target = getDifficultyTargetAsInteger();
            return LARGEST_HASH / (target + BigInteger.One);
        }

        /** Returns a copy of the block, but without any transactions. */
        public Block cloneAsHeader()
        {
            try
            {
                Block block = new Block(param, bitcoinSerialize());
                block.transactions = null;
                return block;
            }
            catch (Exception e)
            {
                // Should not be able to happen unless our state is internally inconsistent.
                throw e;
            }
        }

        /**
        * Returns a multi-line string containing a description of the contents of the block. Use for debugging purposes
        * only.
        */
        public override string ToString()
        {
            StringBuilder s = new StringBuilder("v" + version + " block: \n" +
            " previous block: " + Utils.bytesToHexString(prevBlockHash) + "\n" +
            " merkle root: " + Utils.bytesToHexString(getMerkleRoot()) + "\n" +
            " time: [" + time + "] " + new DateTime(time * 1000).ToString() + "\n" +    // TODO: correct?!?
            " difficulty target (nBits): " + difficultyTarget + "\n" +
            " nonce: " + nonce + "\n");
            if (transactions != null && transactions.Count > 0)
            {
                s.Append(" with ").Append(transactions.Count).Append(" transaction(s):\n");
                foreach (Transaction tx in transactions)
                {
                    s.Append(tx.ToString());
                }
            }
            return s.ToString();
        }

        /**
        * Finds a value of nonce that makes the blocks hash lower than the difficulty target. This is called mining,
        * but solve() is far too slow to do real mining with. It exists only for unit testing purposes and is not a part
        * of the public API.
        *
        * This can loop forever if a solution cannot be found solely by incrementing nonce. It doesn't change extraNonce.
        */
        void solve()
        {
            while (true)
            {
                try
                {
                    // Is our proof of work valid yet?
                    if (checkProofOfWork(false)) return;
                    // No, so increment the nonce and try again.
                    setNonce(getNonce() + 1);
                }
                catch (Exception e)
                {
                    throw e; // Cannot happen.
                }
            }
        }

        /**
        * Returns the difficulty target as a 256 bit value that can be compared to a SHA-256 hash. Inside a block the
        * target is represented using a compact form. If this form decodes to a value that is out of bounds,
        * an exception is thrown.
        */
        public BigInteger getDifficultyTargetAsInteger()
        {
            BigInteger target = Utils.decodeCompactBits(difficultyTarget);
            if (target.CompareTo(new BigInteger(0)) <= 0 || target.CompareTo(param.proofOfWorkLimit) > 0)
                throw new VerificationException("Difficulty target is bad: " + target.ToString());
            return target;
        }

        /** Returns true if the hash of the block is OK (lower than difficulty target). */
        private bool checkProofOfWork(bool throwException)
        {
            // This part is key - it is what proves the block was as difficult to make as it claims
            // to be. Note however that in the context of this function, the block can claim to be
            // as difficult as it wants to be .... if somebody was able to take control of our network
            // connection and fork us onto a different chain, they could send us valid blocks with
            // ridiculously easy difficulty and this function would accept them.
            //
            // To prevent this attack from being possible, elsewhere we check that the difficultyTarget
            // field is of the right value. This requires us to have the preceeding blocks.
            BigInteger target = getDifficultyTargetAsInteger();

            BigInteger h = new BigInteger(getHash());
            if (h.CompareTo(target) > 0)
            {
                // Proof of work check failed!
                if (throwException)
                    throw new VerificationException("Hash is higher than target: " + getHashAsString() + " vs " +
                    target.ToString("X"));
                else
                    return false;
            }
            return true;
        }

        private void checkTimestamp()
        {
            // Allow injection of a fake clock to allow unit testing.
            long currentTime = fakeClock != 0 ? fakeClock : Utils.ConvertToTimestamp(DateTime.Now);
            // TODO: correct? long currentTime = fakeClock != 0 ? fakeClock : System.currentTimeMillis() / 1000;
            if (time > currentTime + ALLOWED_TIME_DRIFT)
                throw new VerificationException("Block too far in future");
        }

        private void checkMerkleHash()
        {
            List<byte[]> tree = buildMerkleTree();
            byte[] calculatedRoot = tree[tree.Count - 1];
            if (!Array.Equals(calculatedRoot, merkleRoot))
            {
                // TODO: log.error("Merkle tree did not verify: ");
                foreach (byte[] b in tree)
                {
                    // TODO: log.error(Utils.bytesToHexString(b));
                }
                throw new VerificationException("Merkle hashes do not match: " +
                Utils.bytesToHexString(calculatedRoot) + " vs " + Utils.bytesToHexString(merkleRoot));
            }
        }

        private byte[] calculateMerkleRoot()
        {
            List<byte[]> tree = buildMerkleTree();
            return tree[tree.Count - 1];
        }

        private List<byte[]> buildMerkleTree()
        {
            // The merkle hash is based on a tree of hashes calculated from the transactions:
            //
            // merkleHash
            // /\
            // / \
            // A B
            // / \ / \
            // tx1 tx2 tx3 tx4
            //
            // Basically transactions are hashed, then the hashes of the transactions are hashed
            // again and so on upwards into the tree. The point of this scheme is to allow for
            // disk space savings later on.
            //
            // This function is a direct translation of CBlock::BuildMerkleTree(). 
            List<byte[]> tree = new List<byte[]>();
            // Start by adding all the hashes of the transactions as leaves of the tree.
            foreach (Transaction t in transactions)
            {
                tree.Add(t.getHash().hash);
            }
            int j = 0;
            // Now step through each level ...
            for (int size = transactions.Count; size > 1; size = (size + 1) / 2)
            {
                // and for each leaf on that level ..
                for (int i = 0; i < size; i += 2)
                {
                    int i2 = Math.Min(i + 1, size - 1);
                    byte[] a = Utils.reverseBytes(tree[j + i]);
                    byte[] b = Utils.reverseBytes(tree[j + i2]);
                    tree.Add(Utils.reverseBytes(Utils.doubleDigestTwoBuffers(a, 0, 32, b, 0, 32)));
                }
                j += size;
            }
            return tree;
        }

        private void checkTransactions()
        {
            // The first transaction in a block must always be a coinbase transaction.
            if (!transactions[0].isCoinBase())
                throw new VerificationException("First tx is not coinbase");
            // The rest must not be.
            for (int i = 1; i < transactions.Count; i++)
            {
                if (transactions[i].isCoinBase())
                    throw new VerificationException("TX " + i + " is coinbase when it should not be.");
            }
        }

        /**
        * Checks the block data to ensure it follows the rules laid out in the network parameters. Specifically, throws
        * an exception if the proof of work is invalid, if the timestamp is too far from what it should be, or if the
        * transactions don't hash to the value in the merkle root field. This is <b>not</b> everything that is required
        * for a block to be valid, only what is checkable independent of the chain.
        *
        * @throws VerificationException
        */
        public void verify()
        {
            // Prove that this block is OK. It might seem that we can just ignore most of these checks given that the
            // network is also verifying the blocks, but we cannot as it'd open us to a variety of obscure attacks.
            //
            // Firstly we need to ensure this block does in fact represent real work done. If the difficulty is high
            // enough, it's probably been done by the network.
            checkProofOfWork(true);
            checkTimestamp();
            // Now we need to check that the body of the block actually matches the headers. The network won't generate
            // an invalid block, but if we didn't validate this then an untrusted man-in-the-middle could obtain the next
            // valid block from the network and simply replace the transactions in it with their own fictional
            // transactions that reference spent or non-existant inputs.
            if (transactions != null)
            {
                Debug.Assert(transactions.Count > 0);
                checkTransactions();
                checkMerkleHash();
            }
        }

        public override bool Equals(object o)
        {
            if (!(o is Block)) return false;
            Block other = (Block)o;
            return Array.Equals(getHash(), other.getHash());
        }

        public override int GetHashCode()
        {
            return getHash().GetHashCode();
        }

        /** Returns the merkle root in big endian form, calculating it from transactions if necessary. */
        public byte[] getMerkleRoot()
        {
            if (merkleRoot == null)
                merkleRoot = calculateMerkleRoot();
            return merkleRoot;
        }

        /** Exists only for unit testing. */
        void setMerkleRoot(byte[] value)
        {
            merkleRoot = value;
            hash = null;
        }

        /** Adds a transaction to this block. */
        internal void addTransaction(Transaction t)
        {
            if (transactions == null)
            {
                transactions = new List<Transaction>();
            }
            transactions.Add(t);
            // Force a recalculation next time the values are needed.
            merkleRoot = null;
            hash = null;
        }

        /** Returns the version of the block data structure as defined by the BitCoin protocol. */
        public long getVersion()
        {
            return version;
        }

        /** Returns the hash of the previous block in the chain, as defined by the block header. */
        public byte[] getPrevBlockHash()
        {
            return prevBlockHash;
        }

        void setPrevBlockHash(byte[] prevBlockHash)
        {
            this.prevBlockHash = prevBlockHash;
            this.hash = null;
        }

        /** Returns the time at which the block was solved and broadcast, according to the clock of the solving node. */
        public long getTime()
        {
            return time;
        }

        public void setTime(long time)
        {
            this.time = time;
            this.hash = null;
        }

        /**
        * Returns the difficulty of the proof of work that this block should meet encoded in compact form. The
        * {@link BlockChain} verifies that this is not too easy by looking at the length of the chain when the block is
        * added. To find the actual value the hash should be compared against, use getDifficultyTargetBI.
        */
        public long getDifficultyTarget()
        {
            return difficultyTarget;
        }

        public void setDifficultyTarget(long compactForm)
        {
            this.difficultyTarget = compactForm;
            this.hash = null;
        }

        /**
        * Returns the nonce, an arbitrary value that exists only to make the hash of the block header fall below the
        * difficulty target.
        */
        public long getNonce()
        {
            return nonce;
        }

        public void setNonce(long nonce)
        {
            this.nonce = nonce;
            this.hash = null;
        }

        /////////////////////////////////////////////////////////////////////////////////////////////////
        // Unit testing related methods.

        static private int coinbaseCounter;
        /** Adds a coinbase transaction to the block. This exists for unit tests. */
        void addCoinbaseTransaction(Address to)
        {
            transactions = new List<Transaction>();
            Transaction coinbase = new Transaction(param);
            // A real coinbase transaction has some stuff in the scriptSig like the extraNonce and difficulty. The
            // transactions are distinguished by every TX output going to a different key.
            //
            // Here we will do things a bit differently so a new address isn't needed every time. We'll put a simple
            // counter in the scriptSig so every transaction has a different hash. The output is also different.
            // Real coinbase transactions use <pubkey> OP_CHECKSIG rather than a send to an address though there's
            // nothing in the system that enforces that and both are just as valid.
            coinbase.inputs.Add(new TransactionInput(param, coinbase, new byte[] { (byte)coinbaseCounter++ }));
            coinbase.outputs.Add(new TransactionOutput(param, coinbase, Utils.toNanoCoins(50, 0), to));
            transactions.Add(coinbase);
        }

        /** Returns a solved block that builds on top of this one. This exists for unit tests. */
        Block createNextBlock(Address to, long time)
        {
            Block b = new Block(param);
            b.setDifficultyTarget(difficultyTarget);
            b.addCoinbaseTransaction(to);
            b.setPrevBlockHash(getHash());
            b.setTime(time);
            b.solve();
            try
            {
                b.verify();
            }
            catch (VerificationException e)
            {
                throw e; // Cannot happen.
            }
            return b;
        }

        Block createNextBlock(Address to)
        {
            // TODO: correct? return createNextBlock(to, System.currentTimeMillis() / 1000);
            return createNextBlock(to, Utils.ConvertToTimestamp(DateTime.Now));
        }
    }
}